//https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=295&tqId=1267319&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany
//主持人调度
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算成功举办活动需要多少名主持人
 * @param n int整型 有n个活动
 * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
 * @param startEndRowLen int startEnd数组行数
 * @param startEndColLen int* startEnd数组列数
 * @return int整型
 */

void swap(int* e1, int* e2)
{
    int tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
}

void InsertSort(int* arr, int len) {
    for (int i = 1; i < len; i++)
    {
        int cur = i;
        while (arr[cur - 1] > arr[cur] && cur >= 1)
        {
            swap(&arr[cur], &arr[cur-1]);
            cur--;
        }
    }
}

int ParSort(int* arr, int left, int right)
{
    int key = left;
    while(left < right)
    {
        while(left < right&&arr[right] >= arr[key]){right--;}
        while(left < right&&arr[left] <= arr[key]){left++;}

        if(left < right)
        {
            swap(&arr[left], &arr[right]);
        }
    }
    swap(&arr[key], &arr[right]);
    return right;
}

void QuickSort(int* arr, int begin, int end) {
    if(begin >= end)
    {
        return;
    }

    if(end - begin < 9)
    {
        InsertSort(arr + begin, end - begin + 1);
        return;
    }

    int key = ParSort(arr, begin, end);

    QuickSort(arr, key + 1, end);
    QuickSort(arr, begin, key - 1);
}

int minmumNumberOfHost(int n, int** startEnd, int startEndRowLen,
                       int* startEndColLen ) {
    // write code here
    int count = 0;
    int start[n];
    int end[n];
    for (int i = 0; i < n; i++) {
        start[i] = startEnd[i][0];
        end[i] = startEnd[i][1];
    }
    QuickSort(start, 0, n - 1);
    QuickSort(end, 0, n - 1);

    int j = 0;
    for (int i = 0; i < n; i++) {
        if (start[i] >= end[j]) {
            j++;
        } else {
            count++;
        }
    }

    return count;
}